package com.njupt.graphTheory;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @Author: wujiaming
 * @CreateTime: 2025/2/1 10:42
 * @Description: 994. 腐烂的橘子
 * 多源广度优先遍历
 * @Version: 1.0
 */


public class OrangesRotting_994 {

    public static final int[][] DIR = {{0,1},{1,0},{-1,0},{0,-1}};

    public class Point{
        int x;
        int y;
        Point(int x,int y){
            this.x = x;
            this.y = y;
        }
    }

    public int orangesRotting(int[][] grid) {


        //1、找到图中第一个腐烂的橘子
        int m = grid.length;
        int n = grid[0].length;
        boolean[][] isVisited = new boolean[m][n];
        Deque<Point> queue = new LinkedList<>();
        boolean isContainOne = false;  //标记是否有好橘子
        int x = -1;
        int y = -1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(grid[i][j] == 2){
                    x = i;
                    y = j;
                    queue.addLast(new Point(x,y));
                    isVisited[x][y] = true;
                }
                if(grid[i][j] == 1){
                    isContainOne = true;
                }
            }
        }
        if(x == -1 && y == -1 && isContainOne){//没有坏橘子，只有好橘子的情况下，没有腐烂的橘子
            return -1;
        }else if(x == -1 && y == -1 && !isContainOne){  //有坏橘子，没有好橘子的情况下
            return 0;
        }
        //2、从该橘子开始进行广度优遍历

        int result = bfs(grid,isVisited,queue);

        //3、得到的结果result，然后再次遍历图中的每一个节点，如果发现没有腐烂的橘子返回-1
        return result;

    }

    private int bfs(int[][] grid, boolean[][] isVisited, Deque<Point> queue) {
        int result = -1; //取-1的原因是，当最后一轮时所有改变质的橘子都已经变质了，此时队列中还有元素（最后 一轮感染的橘子）。需要进行再一次的遍历，这样的话result的值就会多加一次

        while(!queue.isEmpty()){
            //1、得到上一分钟腐烂的橘个数
            int size = queue.size();
            //2、、遍历每一个腐烂的橘子
            for (int i = 0; i < size; i++) {
                //3、每一个腐烂的橘子向四周扩散继续腐烂
                Point point = queue.pollFirst();
                int curX = point.x;
                int curY = point.y;
                //3.1、将四周腐烂的橘子放入队列中
                for (int j = 0; j < DIR.length; j++) {
                    int nextX = DIR[j][0] + curX;
                    int nextY = DIR[j][1] + curY;

                    //3.2 判断坐标是否越界
                    if(nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length) continue;
                    //3.3、没有越界，将周围的橘子腐烂，然后放入队列中
                    if(grid[nextX][nextY] == 1 && !isVisited[nextX][nextY]){
                        grid[nextX][nextY] = 2;
                        isVisited[nextX][nextY] = true;
                        queue.addLast(new Point(nextX,nextY));
                    }
                }
            }
            //4、上一分钟腐烂的橘子扩散完成，result+1
            result++;

        }

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if(grid[i][j] == 1){
                    return -1;
                }

            }
        }

        return result;
    }

    public static void main(String[] args) {
        int[][] grid = {{2,1,1},{1,1,0},{0,1,1}};
//        int[][] grid = {{2,1,1},{0,1,1},{1,0,1}};
//        int[][] grid = {{2,1,1},{1,1,1},{0,1,2}};
//        int[][] grid = {{1}};
        OrangesRotting_994 test = new OrangesRotting_994();
        System.out.println(test.orangesRotting(grid));
    }
}
